Computer generated images are typically made up of many differing components or graphical objects which are composited together and rendered to create a final image. Each graphical object is generally represented as a fill type and a set of outlines. Graphical objects may be rendered by combining them onto a page using compositing operations. An “opacity channel” (also known as a “matte”, an “alpha channel”, or simply “opacity”) is also commonly used as part of the representation of a graphical object. The opacity channel contains information regarding the transparent nature of each element. The opacity channel is typically stored alongside each instance of a colour, so that, for example, a pixel-based image with opacity stores an opacity value as part of the representation of each pixel. In this fashion each graphical object may be interpreted as occupying the entire image area, and the outlines of the graphical object can therefore define a region outside of which the object is fully transparent. This region is called the “active region” of the object. A graphical object without explicit opacity channel information is typically understood to be fully opaque within the outlines of the object, and assumed to be completely transparent outside those outlines.
One means for systematically representing an image in terms of its constituent elements and which facilitates in later rendering is an “expression tree”. Expression trees typically comprise a plurality of nodes including leaf nodes, unary nodes and binary nodes. Nodes of higher degree, or of alternative definition, may also be used. A leaf node, being the outermost node of an expression tree, has no descendent nodes and represents a primitive constituent of an image. Unary nodes represent an operation which modifies the pixel data coming out of the part of the tree below the unary operator. Unary nodes include such operations as colour conversions and convolutions blurring, etc). A binary node typically branches to left and right subtrees, wherein each subtree is itself an expression tree comprising at least one leaf node. Binary nodes represent an operation which combines the pixel data of its two children to form a single result. For example, a binary node may be one of the standard compositing operators such as over, in, out, atop and alpha-XOR, examples of which and others are seen in FIG. 2. The compositing operations represented by the Porter-Duff compositing operators are arithmetic or bitwise operations including opacity, which are performed on the component values of the colours of a graphical object.
Several of the above types of nodes may be combined to form the expression tree. An example of this is shown in FIG. 1. The result of the left-hand side of the expression tree illustrated in FIG. 1 may be interpreted as an image (Image 1) being colour (Conversion) clipped (In) to spline boundaries (Path). This construct is composited with a second image (Image 2).
Although the active region of a graphical object may of itself be of a certain size, it need not be entirely visible in a final image, or only a portion of the active region may have an effect on the final image. For example, assume an image of a certain size is to be displayed on a display. If the image is positioned so that only the top left corner of the image is displayed by the display device, the remainder of the image is not displayed. The final image as displayed on the display device thus comprises the visible portion of the image, and the invisible portion in such a case need not be rendered.
Another way in which only a portion of the active region of an object may have an effect is when the portion is obscured by another object. For example, a final image to be displayed (or rendered) may comprise one or more opaque graphical objects, some of which obscure other graphical objects. Hence, the obscured objects have no effect on the final image.
Two conventional rendering models include “frame buffer rendering” and “pixel sequential rendering”. Conventional frame buffer rendering is based on the “painter's algorithm” which involves rendering multiple objects one at a time into a frame buffer. A compositing operation is carried out for every pixel within the boundaries of an object. A simple frame buffer approach is not sophisticated enough to render arbitrary expressions consisting of compositing operations involving transparency, and extra frame buffers may be required to render such expressions. The extra frame buffers are needed to store intermediate results.
Pixel sequential rendering as opposed to the “object sequential rendering” used in conventional frame buffer based systems involves performing all of the compositing operations required to produce a single pixel before moving on to the next pixel. Interactive frame rates of the order of 15 frames per second and greater can be achieved by such conventional methods, because the actual pixel operations are quite simple. Thus, conventional systems are fast enough to produce acceptable frame rates without requiring complex code. However, this is certainly not true in a compositing environment consisting of complex expression trees since the per-pixel cost of compositing is quite high. Complex compositing expressions can lead to redundant pixel compositing operations thus reducing the speed of rendering. This is because typically an image is rendered in 24-bit colour in addition to an 8-bit alpha channel, thus giving 32 bits per pixel. Therefore, each compositing operator of an expression tree has to deal with each of the four channels.
Problems arise with prior art methods that use the conventional methods. These methods are highly inefficient since the per-pixel cost of evaluating the set of compositing operations required to compute each pixel is too high. Further, pixel sequential rendering is designed to work correctly under the assumption that a particular compositing operation used to render a pixel does not affect pixels outside of the boundaries of the object that is being composited. This assumption is not true for all compositing operations. For example, given two graphic objects. A and B, the compositing expression “A rin B”, makes pixels outside the boundaries of object A transparent. For this type of compositing expression for which the above assumption does not hold, problems arise when generating compositing instructions.